# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : HJ52.py
# @Time     : 2024/3/3 13:03
# @Author   : Robot-Zsj
"""
description:

Levenshtein距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

许多的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance

输入描述
abcdefg
abcdef

输出描述
1


思路：动态规划
"""
from pprint import pprint


def main():
    A = input()
    B = input()
    m = len(A)
    n = len(B)
    dp = [[1 for i in range(n + 1)] for j in range(m + 1)]

    # 这里可以这么理解，当一边的字符为空时，它们之间的编辑距离就等于另一边的字符的长度
    for i in range(n + 1):
        dp[0][i] = i
    for j in range(m + 1):
        dp[j][0] = j
    # 构造二维动态规划矩阵，设置
    """
    m\n [[0, 1, 2, 3, 4, 5, 6],
         [1, 1, 1, 1, 1, 1, 1],
         [2, 1, 1, 1, 1, 1, 1],
         [3, 1, 1, 1, 1, 1, 1],
         [4, 1, 1, 1, 1, 1, 1],
         [5, 1, 1, 1, 1, 1, 1],
         [6, 1, 1, 1, 1, 1, 1],
         [7, 1, 1, 1, 1, 1, 1]]
    """
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            """
            i-1,j-1  i-1, j
                    \    |
            i, j-1 -  i, j
            
            """
            if A[i - 1] == B[j - 1]:  # 如果两个字符串相同，直接取dp[i-1][j-1]的值
                dp[i][j] = dp[i - 1][j - 1]
            else:  # 如果不相同，则取之前三个方向的最小值并加1
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
    print(dp[m][n])


while True:
    try:
        main()
    except:
        break
